Computer graphics uses a variety of methods to generate two-dimensional representations of a three-dimensional scene. For example, a three-dimensional scene represented as a plurality of geometric primitives (e.g., points, lines, triangles, quads, meshes, etc.) may be rasterized to project the geometric primitives to a projection plane and then shaded to calculate a color for one or more pixels of the projection plane based on the rasterization. Alternatively, another technique for generating two-dimensional representations of the three-dimensional scenes is to perform ray-tracing. As is known in the art, ray-tracing is a technique that includes the operation of sending out rays from a particular viewpoint and intersecting the rays with the geometry of the scene. When an intersection is detected, lighting and shading operations may be performed to generate a color value for a pixel of the projection plane intersected by the ray. Additionally, other rays may be generated based on the intersected primitives that contribute to the color of the intersected pixel or other pixels.
Because the number of geometric primitives in a scene may be quite large (e.g., on the order of millions of triangles, etc.) and the number of rays generated to test for intersection against the primitives is also quite large (e.g., on the order of millions to billions of rays), intersection test efficiency typically defines overall rendering efficiency. Each test is typically performed as a query between a test object, such as a ray or a beam, and a target object, such as a triangle.
In massively parallel architectures, query efficiency can substantially determine overall system performance and inefficient query techniques may lead directly to degraded performance. Thus, there is a need for addressing these issues and/or other issues associated with the prior art.